#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * 后序遍历
 */
class Test01{
public:
	int minDepth(TreeNode* root){
		if(root == NULL){
			return 0;
		}
		int leftDepth = minDepth(root->left);
		int rightDepth = minDepth(root->right);
		if(root->left != NULL && root->right == NULL){
			return 1 + leftDepth;
		}
		if(root->left == NULL && root->right != NULL){
			return 1 + rightDepth;
		}
		return 1 + min(rightDepth,leftDepth);
	}
};

/**
 * 前序遍历
 */

class Test02{
public:
	int result;
	void getMinDepth(TreeNode* root,int depth){
		if(root == NULL){
			return;
		}
		// 中
		if(root->left == NULL && root->right == NULL){
			depth = min(result,depth);
		}
		if(root->left){
			// 左
			getMinDepth(root->left,depth+1);
			
		}
		if(root->right){
			// 右
			getMinDepth(root->right,depth+1);
		}
		return;
	}
	
	
	int minDepth(TreeNode* root){
		if(root == NULL){
			return 0;
		}
		result = INT_MAX;
		getMinDepth(root,1);
		return result;
	}
};
class Test{
public:
	int getDepth(TreeNode* node){
		queue<TreeNode*> que;
		int depth = 0;
		que.push(node);
		while(!que.empty()){
			int size = que.size();
			depth++;
			while(size--){
				TreeNode* cur = que.front();que.pop();
				if(cur->left){
					que.push(cur->left);
				}
				if(cur->right){
					que.push(cur->right);
				}
				if(!cur->left && !cur->right){
					return depth;
				}
			}
		}
		return depth;
	}
};


int main(){
	
	return 0;
}
